
package main.old.new_2023.last.month_8;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @Description: todo 57. 插入区间
 * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
 * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
 *
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/
 * @Param:
 * @return:
 **/
public class Solution0828 {

    //插入区间
    public int[][] insert(int[][] intervals, int[] newInterval) {
        //插入最后面，排序，然后合并
        int[][] newIntervals = new int[intervals.length + 1][2];
        for (int i = 0; i < intervals.length; ++i) {
            newIntervals[i] = intervals[i];
        }
        newIntervals[intervals.length] = newInterval;
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        List<int[]> ans = new ArrayList<>();
        ans.add(newIntervals[0]);
        for (int i = 1; i < newIntervals.length; ++i) {
            int s = newIntervals[i][0], e = newIntervals[i][1];
            if (ans.get(ans.size() - 1)[1] < s) {
                ans.add(newIntervals[i]);
            } else {
                ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], e);
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }



    public static void main(String[] args) {
        int[][] intervals = {{1,3},{6,9}};
        int[] newInterval = {2,5};
        Solution0828 test = new Solution0828();
        int[][] insert = test.insert(intervals, newInterval);
        System.out.println(Arrays.deepToString(insert));

    }


}
